#include <bits/stdc++.h>

using namespace std;


/**
 * 贪心策略有问题！！所以，爆搜试试
 */ 
class Solution_x_1 {
public:
    int maxValue(vector<vector<int>>& grid) {
        int xlen=grid.size(),ylen=grid[0].size();
        int posx=0,posy=0,ans=grid[0][0];
        while(posx< xlen-1 || posy < ylen-1){
            
            if(posx+1<xlen && posy+1<ylen){
                if(grid[posx+1][posy]<grid[posx][posy+1]){
                    posy++;
                }else{
                    posx++;
                }
            }else if(posx+1<xlen && posy+1>=ylen){
                posx++;
            }else if(posx+1>=xlen && posy+1<ylen){
                posy++;
            }
            cout << posx << " " << posy <<endl;
            ans+=grid[posx][posy];
        }
        return ans;
    }
};

/*
啥也不想，直接搜索,超时，转换成dp?
*/
class Solution_x_2 {
    int ans;
public:
    void helper(vector<vector<int>>& grid,int posx,int posy,int xlen,int ylen,int tmp){
        if(posx>=xlen || posy>=ylen) return ;
        tmp+=grid[posx][posy];
        if(posx == xlen-1 && posy == ylen-1 ){
            ans=max(tmp,ans);
            return ;
        }

        helper(grid,posx+1,posy,xlen,ylen,tmp);
        helper(grid,posx,posy+1,xlen,ylen,tmp);
        
    }
    int maxValue(vector<vector<int>>& grid) {
        ans=grid[0][0];
        int xlen=grid.size(),ylen=grid[0].size();
        helper(grid,0,0,xlen,ylen,0);
        return ans;
    }
};
/*
将递归搜索转化为dp循环?
*/
class Solution1 {
public:
    int maxValue(vector<vector<int>>& grid) {
        int xlen=grid.size(),ylen=grid[0].size();
        vector<vector<int>> dp(xlen+1,vector<int>(ylen+1,0));
        dp[0][0]=grid[0][0];
        for(int i=0;i<xlen;i++){
            for(int j=0;j<ylen;j++){
                if(i!=0 || j!=0){
                    if(i-1>=0 && j-1>=0)
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
                    else if(i-1>=0){
                        dp[i][j]=dp[i-1][j]+grid[i][j];
                    }else if(j-1 >= 0){
                        dp[i][j]=dp[i][j-1]+grid[i][j];
                    }
                }
            }
        }
        return dp[xlen-1][ylen-1];
    }
};

/*
    优化一下dp
    空间省不下来，那我就继续优化一下时间
*/
class Solution2 {
public:
    int maxValue(vector<vector<int>>& grid) {
        int xlen=grid.size(),ylen=grid[0].size();
        vector<vector<int>> dp(xlen+1,vector<int>(ylen+1,0));
        dp[0][0]=grid[0][0];
        for(int i=1;i<ylen;i++){
            dp[0][i]=grid[0][i]+dp[0][i-1];
        }
        for(int i=1;i<xlen;i++){
            dp[i][0]+=grid[i][0]+dp[i-1][0];
        }
        for(int i=1;i<xlen;i++){
            for(int j=1;j<ylen;j++){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[xlen-1][ylen-1];
         
    }
};

/*
利用grid可以省下空间
*/
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int xlen=grid.size(),ylen=grid[0].size();
        for(int i=1;i<ylen;i++){
            grid[0][i]+=grid[0][i-1];
        }
        for(int i=1;i<xlen;i++){
            grid[i][0]+=grid[i-1][0];
        }
        for(int i=1;i<xlen;i++){
            for(int j=1;j<ylen;j++){
                grid[i][j]=max(grid[i-1][j],grid[i][j-1])+grid[i][j];
            }
        }
        return grid[xlen-1][ylen-1];
         
    }
};



int main(){

    vector<vector<int>> v={{5,0,1,1,2,1,0,1,3,6,3,0,7,3,3,3,1},{1,4,1,8,5,5,5,6,8,7,0,4,3,9,9,6,0},{2,8,3,3,1,6,1,4,9,0,9,2,3,3,3,8,4},{3,5,1,9,3,0,8,3,4,3,4,6,9,6,8,9,9},{3,0,7,4,6,6,4,6,8,8,9,3,8,3,9,3,4},{8,8,6,8,3,3,1,7,9,3,3,9,2,4,3,5,1},{7,1,0,4,7,8,4,6,4,2,1,3,7,8,3,5,4},{3,0,9,6,7,8,9,2,0,4,6,3,9,7,2,0,7},{8,0,8,2,6,4,4,0,9,3,8,4,0,4,7,0,4},{3,7,4,5,9,4,9,7,9,8,7,4,0,4,2,0,4},{5,9,0,1,9,1,5,9,5,5,3,4,6,9,8,5,6},{5,7,2,4,4,4,2,1,8,4,8,0,5,4,7,4,7},{9,5,8,6,4,4,3,9,8,1,1,8,7,7,3,6,9},{7,2,3,1,6,3,6,6,6,3,2,3,9,9,4,4,8}};
    //vector<vector<int>> v={{1}}; 
    Solution s;
    int start=clock();
    cout << s.maxValue(v)<<endl;
    int end=clock();
    cout << "运行耗时: "<< (double)(end-start)/CLOCKS_PER_SEC *1000 << " ms"<<endl;

    return 0;
}